
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2598. -- [IOI2011]garden -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2598: [IOI2011]garden</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>128 MB<br><span class=green>Submit: </span>10&nbsp;&nbsp;<span class=green>Solved: </span>4<br>[<a href='submitpage.php?id=2598'>Submit</a>][<a href='problemstatus.php?id=2598'>Status</a>][<a href='bbs.php?id=2598'>Discuss</a>]</center><h2>Description</h2><div class=content><p><span style="font-size: medium">植物学家 Somhed&nbsp; 带着几组学生去泰国最大的热带花园游玩。这个花园中有 N&nbsp; 个喷泉（编号为0, 1, &hellip;, N-1）和 M 条小路。每条小路连接一对不同的喷泉，两个喷泉间最多只有一条小路，小路是可以双向行走的。从任意一个喷泉出发至少有一条小路。每条小路的美丽程度决定了Somhed&nbsp; 选择走该条小路的优先程度。每组学生可以从任何一个喷泉出发。 在任何一个喷泉，Somhed 和他的学生们会选择最美丽的一条小路离开该喷泉，除非最美丽的这条小路是他们刚刚走过的，且还有其它小路可走。在这种情况下，他们会选择第二美丽的小路离开该喷泉。当然，如果没有第二美丽的小路可选，他们会选择刚刚走过的小路<br />
再走回去。注意，对于Somhed 来说没有两条小路是同样美丽的。 <br />
Somhed 的学生们对小路的美丽与否不感兴趣，他们喜欢在喷泉 P 旁边的豪华餐厅吃午饭。Somhed&nbsp; 知道他的学生在走过恰好 K&nbsp; 条小路后会感觉饥饿，当然，对于不同组的学生K 可以不同。Somhed&nbsp; 想知道在下列条件下，对于每组学生有多少条不同的路径可选。 <br />
&nbsp; 每组可以从任意喷泉出发； <br />
&nbsp; 但是接下来的路径必须按照上面描述的规则进行选择； <br />
&nbsp; 每组必须在恰好走过 K 条小路后到达喷泉 P 。 <br />
&nbsp;<br />
注意：他们在最终到达喷泉P之前可能曾经到过喷泉 P。 <br />
给定喷泉和小路的信息，以及 Q 个不同的 K，你要回答对于每个 K 来说,&nbsp; 有多少条不同的<br />
路径可供候选。 <br />
写一个函数count_routes(N,M,P,R,Q,G)，该函数的参数如下： <br />
&nbsp; N&nbsp; &ndash; 喷泉的数目。喷泉从&nbsp; 0 到&nbsp; N-1 编号。 <br />
&nbsp; M&nbsp; &ndash; 小路的数目。小路从&nbsp; 0 到&nbsp; M-1编号。所有小路按照其美丽程度从大到小的<br />
顺序给出，即对于&nbsp; 0 &le; i &lt; M-1, 小路&nbsp; i&nbsp; 比小路&nbsp; i+1&nbsp; 更美丽。 <br />
&nbsp; P&nbsp; &ndash; 豪华餐厅所在的喷泉编号。 <br />
&nbsp; R&nbsp; &ndash; 描述小路的二维数组。对于&nbsp; 0 &le; i &lt; M,&nbsp;&nbsp; 小路 i 连接喷泉&nbsp; R[i][0] 和喷泉<br />
R[i][1]。 再次提醒：每条小路连接两个不同的喷泉，两个喷泉间最多只有一条小<br />
路。 <br />
&nbsp; Q&nbsp; &ndash; 学生的组数。 <br />
&nbsp; G&nbsp; &ndash; 一个一维的整数数组，包含 Q 个不同的 K。对于&nbsp; 0 &le; i &lt; Q，G[i]表示第i 组<br />
学生对应的K，即第 i 组学生经过K 条小路后要到达喷泉P。 <br />
对于&nbsp; 0&nbsp; &le;&nbsp; i&nbsp; &lt; Q，你的函数必须给出可能的路径数目，满足第i 组学生在到达喷泉 P&nbsp; 时恰好<br />
走过 G[i]条小路。对于第 i 组学生，你的函数必须调用函数 answer(X)&nbsp; 来给出可能的路径的<br />
数目 X。答案给出的顺序必须和问题给出的顺序相同。如果没有合适的路径，你的函数应该<br />
调用 answer(0)。 <br />
</span></p></div><h2>Input</h2><div class=content><p><img alt="" src="/JudgeOnline/upload/201202/1(2).jpg" /></p>
<p><img alt="" src="/JudgeOnline/upload/201202/2(1).jpg" /></p></div><h2>Output</h2><div class=content></div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>780 780 0<br />
1 0<br />
0 2<br />
2 3<br />
3 1<br />
4 1<br />
5 4<br />
6 5<br />
7 6<br />
8 7<br />
9 8<br />
10 9<br />
11 10<br />
12 11<br />
13 12<br />
14 13<br />
15 14<br />
16 15<br />
17 16<br />
18 17<br />
19 18<br />
20 19<br />
21 20<br />
22 21<br />
23 22<br />
24 23<br />
25 24<br />
26 25<br />
27 26<br />
28 27<br />
29 28<br />
30 29<br />
31 30<br />
32 31<br />
33 32<br />
34 33<br />
35 34<br />
36 35<br />
37 36<br />
38 37<br />
39 38<br />
40 39<br />
41 40<br />
42 41<br />
43 42<br />
44 43<br />
45 44<br />
46 45<br />
47 46<br />
48 47<br />
49 48<br />
50 49<br />
51 50<br />
52 51<br />
53 52<br />
54 53<br />
55 54<br />
56 55<br />
57 56<br />
58 57<br />
59 58<br />
60 59<br />
61 60<br />
62 61<br />
63 62<br />
64 63<br />
65 64<br />
66 65<br />
67 66<br />
68 67<br />
69 68<br />
70 69<br />
71 70<br />
72 71<br />
73 72<br />
74 73<br />
75 74<br />
76 75<br />
77 76<br />
78 77<br />
79 78<br />
80 79<br />
81 80<br />
82 81<br />
83 82<br />
84 83<br />
85 84<br />
86 85<br />
87 86<br />
88 87<br />
89 88<br />
90 89<br />
91 90<br />
92 91<br />
93 92<br />
94 93<br />
95 94<br />
96 95<br />
97 96<br />
98 97<br />
99 98<br />
100 99<br />
101 100<br />
102 101<br />
103 102<br />
104 103<br />
105 104<br />
106 105<br />
107 106<br />
108 107<br />
109 108<br />
110 109<br />
111 110<br />
112 111<br />
113 112<br />
114 113<br />
115 114<br />
116 115<br />
117 116<br />
118 117<br />
119 118<br />
120 119<br />
121 120<br />
122 121<br />
123 122<br />
124 123<br />
125 124<br />
126 125<br />
127 126<br />
128 127<br />
129 128<br />
130 129<br />
131 130<br />
132 131<br />
133 132<br />
134 133<br />
135 134<br />
136 135<br />
137 136<br />
138 137<br />
139 138<br />
140 139<br />
141 140<br />
142 141<br />
143 142<br />
144 143<br />
145 144<br />
146 145<br />
147 146<br />
148 147<br />
149 148<br />
150 149<br />
151 150<br />
152 151<br />
153 152<br />
154 153<br />
155 154<br />
156 155<br />
157 156<br />
158 157<br />
159 158<br />
160 159<br />
161 160<br />
162 161<br />
163 162<br />
164 163<br />
165 164<br />
166 165<br />
167 166<br />
168 167<br />
169 168<br />
170 169<br />
171 170<br />
172 171<br />
173 172<br />
174 173<br />
175 174<br />
176 175<br />
177 176<br />
178 177<br />
179 178<br />
180 179<br />
181 180<br />
182 181<br />
183 182<br />
184 183<br />
185 184<br />
186 185<br />
187 186<br />
188 187<br />
189 188<br />
190 189<br />
191 190<br />
192 191<br />
193 192<br />
194 193<br />
195 194<br />
196 195<br />
197 196<br />
198 197<br />
199 198<br />
200 199<br />
201 200<br />
202 201<br />
203 202<br />
204 203<br />
205 204<br />
206 205<br />
207 206<br />
208 207<br />
209 208<br />
210 209<br />
211 210<br />
212 211<br />
213 212<br />
214 213<br />
215 214<br />
216 215<br />
217 216<br />
218 217<br />
219 218<br />
220 219<br />
221 220<br />
222 221<br />
223 222<br />
224 223<br />
225 224<br />
226 225<br />
227 226<br />
228 227<br />
229 228<br />
230 229<br />
231 230<br />
232 231<br />
233 232<br />
234 233<br />
235 234<br />
236 235<br />
237 236<br />
238 237<br />
239 238<br />
240 239<br />
241 240<br />
242 241<br />
243 242<br />
244 243<br />
245 244<br />
246 245<br />
247 246<br />
248 247<br />
249 248<br />
250 249<br />
251 250<br />
252 251<br />
253 252<br />
254 253<br />
255 254<br />
256 255<br />
257 256<br />
258 257<br />
259 258<br />
260 259<br />
261 260<br />
262 261<br />
263 262<br />
264 263<br />
265 264<br />
266 265<br />
267 266<br />
268 267<br />
269 268<br />
270 269<br />
271 270<br />
272 271<br />
273 272<br />
274 273<br />
275 274<br />
276 275<br />
277 276<br />
278 277<br />
279 278<br />
280 279<br />
281 280<br />
282 281<br />
283 282<br />
284 283<br />
285 284<br />
286 285<br />
287 286<br />
288 287<br />
289 288<br />
290 289<br />
291 290<br />
292 291<br />
293 292<br />
294 293<br />
295 294<br />
296 295<br />
297 296<br />
298 297<br />
299 298<br />
300 299<br />
301 300<br />
302 301<br />
303 302<br />
304 303<br />
305 304<br />
306 305<br />
307 306<br />
308 307<br />
309 308<br />
310 309<br />
311 310<br />
312 311<br />
313 312<br />
314 313<br />
315 314<br />
316 315<br />
317 316<br />
318 317<br />
319 318<br />
320 319<br />
321 320<br />
322 321<br />
323 322<br />
324 323<br />
325 324<br />
326 325<br />
327 326<br />
328 327<br />
329 328<br />
330 329<br />
331 330<br />
332 331<br />
333 332<br />
334 333<br />
335 334<br />
336 335<br />
337 336<br />
338 337<br />
339 338<br />
340 339<br />
341 340<br />
342 341<br />
343 342<br />
344 343<br />
345 344<br />
346 345<br />
347 346<br />
348 347<br />
349 348<br />
350 349<br />
351 350<br />
352 351<br />
353 352<br />
354 353<br />
355 354<br />
356 355<br />
357 356<br />
358 357<br />
359 358<br />
360 359<br />
361 360<br />
362 361<br />
363 362<br />
364 363<br />
365 364<br />
366 365<br />
367 366<br />
368 367<br />
369 368<br />
370 369<br />
371 370<br />
372 371<br />
373 372<br />
374 373<br />
375 374<br />
376 375<br />
377 376<br />
378 377<br />
379 378<br />
380 379<br />
381 380<br />
382 381<br />
383 382<br />
384 383<br />
385 384<br />
386 385<br />
387 386<br />
388 387<br />
389 388<br />
390 389<br />
391 390<br />
392 391<br />
393 392<br />
394 393<br />
395 394<br />
396 395<br />
397 396<br />
398 397<br />
399 398<br />
400 399<br />
401 400<br />
402 401<br />
403 402<br />
404 403<br />
405 404<br />
406 405<br />
407 406<br />
408 407<br />
409 408<br />
410 409<br />
411 410<br />
412 411<br />
413 412<br />
414 413<br />
415 414<br />
416 415<br />
417 416<br />
418 417<br />
419 418<br />
420 419<br />
421 420<br />
422 421<br />
423 422<br />
424 423<br />
425 424<br />
426 425<br />
427 426<br />
428 427<br />
429 428<br />
430 429<br />
431 430<br />
432 431<br />
433 432<br />
434 433<br />
435 434<br />
436 435<br />
437 436<br />
438 437<br />
439 438<br />
440 439<br />
441 440<br />
442 441<br />
443 442<br />
444 443<br />
445 444<br />
446 445<br />
447 446<br />
448 447<br />
449 448<br />
450 449<br />
451 450<br />
452 451<br />
453 452<br />
454 453<br />
455 454<br />
456 455<br />
457 456<br />
458 457<br />
459 458<br />
460 459<br />
461 460<br />
462 461<br />
463 462<br />
464 463<br />
465 464<br />
466 465<br />
467 466<br />
468 467<br />
469 468<br />
470 469<br />
471 470<br />
472 471<br />
473 472<br />
474 473<br />
475 474<br />
476 475<br />
477 476<br />
478 477<br />
479 478<br />
480 479<br />
481 480<br />
482 481<br />
483 482<br />
484 483<br />
485 484<br />
486 485<br />
487 486<br />
488 487<br />
489 488<br />
490 489<br />
491 490<br />
492 491<br />
493 492<br />
494 493<br />
495 494<br />
496 495<br />
497 496<br />
498 497<br />
499 498<br />
500 499<br />
501 500<br />
502 501<br />
503 502<br />
504 503<br />
505 504<br />
506 505<br />
507 506<br />
508 507<br />
509 508<br />
510 509<br />
511 510<br />
512 511<br />
513 512<br />
514 513<br />
515 514<br />
516 515<br />
517 516<br />
518 517<br />
519 518<br />
520 519<br />
521 520<br />
522 521<br />
523 522<br />
524 523<br />
525 524<br />
526 525<br />
527 526<br />
528 527<br />
529 528<br />
530 529<br />
531 530<br />
532 531<br />
533 532<br />
534 533<br />
535 534<br />
536 535<br />
537 536<br />
538 537<br />
539 538<br />
540 539<br />
541 540<br />
542 541<br />
543 542<br />
544 543<br />
545 544<br />
546 545<br />
547 546<br />
548 547<br />
549 548<br />
550 549<br />
551 550<br />
552 551<br />
553 552<br />
554 553<br />
555 554<br />
556 555<br />
557 556<br />
558 557<br />
559 558<br />
560 559<br />
561 560<br />
562 561<br />
563 562<br />
564 563<br />
565 564<br />
566 565<br />
567 566<br />
568 567<br />
569 568<br />
570 569<br />
571 570<br />
572 571<br />
573 572<br />
574 573<br />
575 574<br />
576 575<br />
577 576<br />
578 577<br />
579 578<br />
580 579<br />
581 580<br />
582 581<br />
583 582<br />
584 583<br />
585 584<br />
586 585<br />
587 586<br />
588 587<br />
589 588<br />
590 589<br />
591 590<br />
592 591<br />
593 592<br />
594 593<br />
595 594<br />
596 595<br />
597 596<br />
598 597<br />
599 598<br />
600 599<br />
601 600<br />
602 601<br />
603 602<br />
604 603<br />
605 604<br />
606 605<br />
607 606<br />
608 607<br />
609 608<br />
610 609<br />
611 610<br />
612 611<br />
613 612<br />
614 613<br />
615 614<br />
616 615<br />
617 616<br />
618 617<br />
619 618<br />
620 619<br />
621 620<br />
622 621<br />
623 622<br />
624 623<br />
625 624<br />
626 625<br />
627 626<br />
628 627<br />
629 628<br />
630 629<br />
631 630<br />
632 631<br />
633 632<br />
634 633<br />
635 634<br />
636 635<br />
637 636<br />
638 637<br />
639 638<br />
640 639<br />
641 640<br />
642 641<br />
643 642<br />
644 643<br />
645 644<br />
646 645<br />
647 646<br />
648 647<br />
649 648<br />
650 649<br />
651 650<br />
652 651<br />
653 652<br />
654 653<br />
655 654<br />
656 655<br />
657 656<br />
658 657<br />
659 658<br />
660 659<br />
661 660<br />
662 661<br />
663 662<br />
664 663<br />
665 664<br />
666 665<br />
667 666<br />
668 667<br />
669 668<br />
670 669<br />
671 670<br />
672 671<br />
673 672<br />
674 673<br />
675 674<br />
676 675<br />
677 676<br />
678 677<br />
679 678<br />
680 679<br />
681 680<br />
682 681<br />
683 682<br />
684 683<br />
685 684<br />
686 685<br />
687 686<br />
688 687<br />
689 688<br />
690 689<br />
691 690<br />
692 691<br />
693 692<br />
694 693<br />
695 694<br />
696 695<br />
697 696<br />
698 697<br />
699 698<br />
700 699<br />
701 700<br />
702 701<br />
703 702<br />
704 703<br />
705 704<br />
706 705<br />
707 706<br />
708 707<br />
709 708<br />
710 709<br />
711 710<br />
712 711<br />
713 712<br />
714 713<br />
715 714<br />
716 715<br />
717 716<br />
718 717<br />
719 718<br />
720 719<br />
721 720<br />
722 721<br />
723 722<br />
724 723<br />
725 724<br />
726 725<br />
727 726<br />
728 727<br />
729 728<br />
730 729<br />
731 730<br />
732 731<br />
733 732<br />
734 733<br />
735 734<br />
736 735<br />
737 736<br />
738 737<br />
739 738<br />
740 739<br />
741 740<br />
742 741<br />
743 742<br />
744 743<br />
745 744<br />
746 745<br />
747 746<br />
748 747<br />
749 748<br />
750 749<br />
751 750<br />
752 751<br />
753 752<br />
754 753<br />
755 754<br />
756 755<br />
757 756<br />
758 757<br />
759 758<br />
760 759<br />
761 760<br />
762 761<br />
763 762<br />
764 763<br />
765 764<br />
766 765<br />
767 766<br />
768 767<br />
769 768<br />
770 769<br />
771 770<br />
772 771<br />
773 772<br />
774 773<br />
775 774<br />
776 775<br />
777 776<br />
778 777<br />
779 778<br />
1<br />
96<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>25<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=2598'>Submit</a>][<a href='problemstatus.php?id=2598'>Status</a>][<a href='bbs.php?id=2598'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
